import { Compare, defaultCompare } from "../../utils/compare.js";
import BinarySearchTree from "./BinarySearchTree.js";
import BinaryTreeNode from "./BinaryTreeNode.js";

/**
 * 平衡因子
 */
const BalanceFactor = {
  UNBALANCED_RIGHT: 1, // 右侧不平衡
  SLIGHTLY_UNBALANCED_RIGHT: 2, // 右侧稍不平衡
  BALANCED: 3, // 平衡的
  SLIGHTLY_UNBALANCED_LEFT: 4, // 左侧稍不平衡
  UNBALANCED_LEFT: 5, // 左侧不平衡
};

export default class AVLTree extends BinarySearchTree {
  constructor(compareFn = defaultCompare) {
    super(compareFn);
  }

  //#region getNodeHeight(node) 计算节点高度
  /**
   * 计算节点的高度
   * @param {BinaryTreeNode}} node
   * @returns {number}
   */
  getNodeHeight(node) {
    if (node == null) {
      return -1;
    }
    return Math.max(this.getNodeHeight(node.left), this.getNodeHeight(node.right)) + 1;
  }
  //#endregion

  //#region getBalanceFactor(node) 计算一个节点的平衡因子
  /**
   * 计算一个节点的平衡因子
   * @param {BinaryTreeNode} node
   * @returns {BalanceFactor}
   */
  getBalanceFactor(node) {
    const heightDiff = this.getNodeHeight(node.left) - this.getNodeHeight(node.right);
    switch (heightDiff) {
      case -2:
        return BalanceFactor.UNBALANCED_RIGHT;
      case -1:
        return BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT;
      case 1:
        return BalanceFactor.SLIGHTLY_UNBALANCED_LEFT;
      case 2:
        return BalanceFactor.UNBALANCED_LEFT;
      default:
        return BalanceFactor.BALANCED;
    }
  }
  //#endregion

  //#region rotationLL(node) 向右的单旋转
  /**
   * 左-左(LL)：向右的单旋转
   *
   *          n                         t
   *         / \                       / \
   *        t   c -> rotationLL(n) -> a   n
   *       / \                           / \
   *      a   b                         b   c
   *
   * @param {BinaryTreeNode} node
   * @returns {BinaryTreeNode}
   */
  rotationLL(node) {
    const temp = node.left;
    node.left = temp.right;
    temp.right = node;
    return temp;
  }
  //#endregion

  //#region rotationRR(node) 向左的单旋转
  /**
   * 右-右(RR)：向左的单旋转
   *
   *          n                         t
   *         / \                       / \
   *        a   t -> rotationRR(n) -> n   c
   *           / \                   / \
   *          b   c                 a   b
   *
   * @param {BinaryTreeNode} node
   * @returns {BinaryTreeNode}
   */
  rotationRR(node) {
    const temp = node.right;
    node.right = temp.left;
    temp.left = node;
    return temp;
  }
  //#endregion

  //#region rotationLR(node) 向右的双旋转
  /**
   * 左-右(LR)：向右的双旋转
   *
   *          3                         3                          2
   *         / \                       / \                        / \
   *        1   d -> rotationRR(1) -> 2   d -> rotationLL(3) ->  1   3
   *       / \                       / \                        /\   /\
   *      a   2                     1   c                      a  b c  d
   *         / \                   / \
   *        b   c                 a   b
   *
   * @param {BinaryTreeNode} node
   * @returns {BinaryTreeNode}
   */
  rotationLR(node) {
    node.left = this.rotationRR(node.left);
    return this.rotationLL(node);
  }
  //#endregion

  //#region rotationRL(node) 向左的双旋转
  /**
   * 右-左(RL)：向左的双旋转
   *
   *          1                         1                          2
   *         / \                       / \                        / \
   *        a   3 -> rotationLL(3) -> a   2 -> rotationRR(2) ->  1   3
   *           / \                       / \                    /\   /\
   *          2   d                     b   3                  a  b c  d
   *         / \                           / \
   *        b   c                         c   d
   *
   * @param {BinaryTreeNode} node
   * @returns {BinaryTreeNode}
   */
  rotationRL(node) {
    node.right = this.rotationLL(node.right);
    return this.rotationRR(node);
  }
  //#endregion

  //#region insertNode(node, value) 插入节点操作
  /**
   * 插入节点操作
   * @param {BinaryTreeNode} node 节点
   * @param {*} value
   * @returns {BinaryTreeNode}
   */
  insertNode(node, value) {
    if (node == null) {
      return new BinaryTreeNode(value);
    }
    // 如果小了，继续向左树遍历
    if (this.compareFn(value, node.value) === Compare.LESS_THAN) {
      node.left = this.insertNode(node.left, value);
    }
    // 如果大了，继续向右树遍历
    else if (this.compareFn(value, node.value) === Compare.BIGGER_THAN) {
      node.right = this.insertNode(node.right, value);
    }
    // 最终返回node，此时如果插入的值已经存在，则不进行任何操作
    else {
      return node;
    }

    // 只有当需要插入操作时，才会对树进行平衡操作
    const balanceFactor = this.getBalanceFactor(node);
    // 当左侧极不平衡时，执行右旋操作
    if (balanceFactor === BalanceFactor.UNBALANCED_LEFT) {
      // left子树超重时，执行LL单旋操作
      if (this.compareFn(value, node.left.value) === Compare.LESS_THAN) {
        node = this.rotationLL(node);
      }
      // right子树超重时，执行LR双旋操作
      else {
        node = this.rotationLR(node);
      }
    }

    // 当右侧极不平衡时，执行左旋操作
    if (balanceFactor === BalanceFactor.UNBALANCED_RIGHT) {
      // right子树超重时，执行RR单旋操作
      if (this.compareFn(value, node.right.value) === Compare.BIGGER_THAN) {
        node = this.rotationRR(node);
      }
      // left子树超重时，执行RL双旋操作
      else {
        node = this.rotationRL(node);
      }
    }

    return node;
  }
  //#endregion

  //#region removeNode(node, value) 删除节点操作
  /**
   * 删除节点操作
   * @param {BinaryTreeNode} node 需要查询的节点
   * @param {*} value 需要删除的值
   * @returns {BinaryTreeNode}
   */
  removeNode(node, value) {
    // 调用基类方法，删除节点
    node = super.removeNode(node, value);

    // 当node为null时，不需要额外操作
    if (node == null) {
      return node;
    }

    // 检测树是否平衡
    const balanceFactor = this.getBalanceFactor(node);
    if (balanceFactor === BalanceFactor.UNBALANCED_LEFT) {
      // left子树超重时，执行LL单旋操作（右旋）
      if (this.compareFn(value, node.left.value) === Compare.LESS_THAN) {
        node = this.rotationLL(node);
      }
      // right子树超重时，执行LR双旋操作（右旋）
      else {
        node = this.rotationLR(node);
      }
    }

    // 当右侧极不平衡时，执行左旋操作
    if (balanceFactor === BalanceFactor.UNBALANCED_RIGHT) {
      // right子树超重时，执行RR单旋操作（左旋）
      if (this.compareFn(value, node.right.value) === Compare.BIGGER_THAN) {
        node = this.rotationRR(node);
      }
      // left子树超重时，执行RL双旋操作（左旋）
      else {
        node = this.rotationRL(node);
      }
    }

    return node;
  }
  //#endregion
}
